package algorithm.leetcode.I101to200;

import algorithm.leetcode.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class Q105 {

    Map<Integer, Integer> inorderMap = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
    }


    private TreeNode build(int[] preorder,
                           int preorderStart,
                           int preorderEnd,
                           int[] inorder,
                           int inorderStart,
                           int inorderEnd) {

        // 递归终点
        if (preorderEnd < preorderStart) return null;

        // 向后递归
        // 拿到根节点
        TreeNode root = new TreeNode(preorder[preorderStart]);
        int rootIndex = inorderMap.get(preorder[preorderStart]);
        int leftLen = rootIndex - inorderStart;
        int rightLen = inorderEnd - rootIndex;
        // 构建左子树,可以保证preorder和inorder左切片数组长度恒为leftLen,此外若leftLen==0则会进入递归终点
        root.left = build(preorder, preorderStart+1, preorderStart+leftLen, inorder, inorderStart, inorderStart+leftLen-1);
        // 构建右子树,可以保证preorder和inorder右切片数组长度恒为rightLen,此外若rightLen==0则会进入递归终点
        root.right = build(preorder, preorderStart+leftLen+1, preorderStart+leftLen+rightLen, inorder, rootIndex+1, rootIndex+rightLen);
        return root;
    }
}
